package com.hzj.alg;

public class searchRange {
    public static void main(String[] args) {
        int[] a = new int[]{5,7,7,8,8,10};
        int[] ints = new searchRange().searchRange1(a, 8);
        System.out.println(ints.toString());
    }
    public int[] searchRange(int[] nums,int target) {
        int first = -1 ,last = -1;
        if (nums.length == 0) {
            return new int[]{-1,-1};
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                first = i;
                break;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                last = i;
                System.out.println(last);
            }
        }
        int[] b = new int[]{first,last};
        return b;
    }
    /**
     * 二分
     */
    public int[] searchRange1(int[] nums,int target) {
        int leftIdx = binarySearch(nums,target,true) ;
        int rightIdx = binarySearch(nums,target,false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[] {leftIdx,rightIdx};
        }
        return new int[]{-1,-1};
    }
    public int binarySearch(int[] nums,int target,boolean lower) {
        int left = 0,right = nums.length - 1,ans = nums.length;
        while (left <= right) {
            int mid = (left + right)/2;
            if (nums[mid] > target || (lower && nums[mid] >=target)) {
                right = mid - 1;
                ans = mid;
            }else left = mid + 1;
        }
        return ans;
    }
}

